#include <iostream>
#include <fstream>
using namespace std;

void qsort(int* buf,int len);

int main(int argc,char* argv[])
{
	ifstream file("rand.txt");
	int buf[1000];
	int a;
	int i = 0;
	int len = sizeof(buf)/sizeof(int);
	while(!file.eof())
	{
		file>>a;
		if(file.good() && i < len)
			buf[i++] = a;
	}

	qsort(buf,len);

	for(int i = 0;i < len;i++)
	{
		if(i > 0 && buf[i] < buf[i-1])
		{	
			cout<<"fail"<<endl;
			break;
		}
		cout<<buf[i]<<endl;
	}
	return 0;
}

void qsort(int* buf,int len)
{
	if(len <= 1)
		return;
	else if(len == 2)
	{
		if(buf[0] > buf[1])
		{
			int temp = buf[0];
			buf[0] = buf[1];
			buf[1] = temp;
		}
		return;
	}
	
	int i = 0;
	int m = buf[i];
	int j = len - 1;
	while(i < j)
	{
		int cur = buf[i+1];
		if(cur <= m)
		{
			buf[i] = cur;
			buf[i+1] = m;
			i++;
			continue;
		}

		buf[i+1] = buf[j];
		buf[j] = cur;
		j--;
	}
	qsort(buf,i);
	qsort(buf + j+1,len - j-1);
}

